Gekkan Dennou Club 145

home *** CD-ROM | disk | FTP | other *** search

/ Gekkan Dennou Club 145 / Gekkan Dennou Club - 2000.6 Vol. 145 (Japan) (Track 1).bin / docs / perl / perl18.doc < prev

Wrap

Text File | 2000-04-22 | 27.0 KB | 928 lines

おきらくＰｅｒｌプログラミング入門～～めざせ Perl マスター～～広井誠第１８回 ○オブジェクト指向編（その４）前回は説明のためのプログラムしか示すことができなかったので、今回は継承を使って具体的なプログラムを作ります。ところが、おもしろいアイデアがなかなか浮かばずに先月は休載いたしましたが、今月も同じように苦しい状態です。ここは開き直って、第 16 回で作成した二分探索木を継承して、「AVL 平衡木」を作ることにしました。AVL 平衡木の操作は複雑で、継承の例題とするには不適切かもしれませんが、リファレンスの応用例にはなるでしょう。 ○AVL 平衡木二分探索木では、最下層にあるデータを探す場合が最悪で、木の高さ分だけ比較が行われます。したがって、木の高さを低く抑えた方が探索効率も良くなります。木の高さはデータ数を N とすると、データがランダムに挿入されればlog N 程度に収まります。しかし、昇順にソートされたデータを挿入していくと、右側の木にだけデータが追加され、線形探索と同じになってしまいます。二分探索木の性能を十分に発揮させるには、左右の木のバランスが重要なのです。そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、2-3 木、B 木、B* 木などがあります。この中で 2-3 木、B 木、B* 木は多分木、AVL 木は二分木を使用します。 AVL 木は、1962 年に Adel'son-Vel'skii と Landis が考案したもので、考案者の頭文字をとって AVL 木と呼ばれています。AVL 木は最初に実現された平衡木として歴史的な意味で価値がありますが、性能的には B 木や B* 木の方が優れています。多分木を使う場合、原理的に難しいことはないのですが、実際のプログラムは相当に複雑になります。興味のある方は参考文献[2] を読んでみてください。 AVL 木は「Ｚしーモンキーほしゅうの時間その１０(月刊・電脳倶楽部 Vol.95 ZFIX10.DOC )」でも説明しました。そこで、AVL 木の説明は ZFIX10.DOC から抜粋します。 ━━ ここから ZFIX10.DOC の抜粋 ━━ 木の高さを一定レベルに抑えるデータ構造に「AVL 平衡木」があります。この方法は、左右の部分木の高さを計算し、その差が 1 より大きくなったならば、それを 1 以下になるように修正することで、全体の木の高さを抑えようとするものです。 n 個の節を持つ二分探索木の高さは、節が左右に均等に分配されれば、log n 程度に収まります。参考文献 [1] によれば、「AVL 平衡木では、この 1.5 倍程度の高さに収まる。」とのことです。したがって、100 万個のデータに対して木の高さは 30 程度に収まることになります。それでは、どのように木の構成を修正するのか、見ていくことにしましょう。左右の木の高さの差を「平衡度」という数値を使って表しましょう。新しい節を追加した場合、その親の節で平衡度が崩れます。新しい節は子を持っていないので、平衡度は均衡していると考えられるので 0 とします。そして、左側に新しい子を追加した場合は、平衡度を 1 増やすことにし、右側に新しい子を追加した場合は 1 減らすことにします。このようにすると、平衡度が 1 ならば左部分木が 1 つ高く、-1 ならば右部分木が 1 つ高い、ということになります。このあと根の方向に向かって平衡度が崩れていないかチェックしていきます。そして、平衡度が -2 または 2 になったら、左右の部分木の高さを修正します。それでは、修正が必要な場合を考えていきましょう。平衡度平衡度ＡＡ：1 ＡＡ：2 ／＼／＼ＢＣＢ：0 ＢＣＢ：1 ／＼／＼ＤＥＤ：0 ＤＥＤ：1 ／ＦＦ：0 図 1 : ＬＬ１重回転（修正前）上図を見てください。節Ａの平衡度は 1 で、その他の節の平衡度は 0 です。この状態で、節Ｄの左側に節Ｆを追加します。Ｄの平衡度は 1 になります。その親のＢは、左側の部分木で節が追加されたので、この平衡度も 1 になります。そして、その親のＡも左部分木で追加が行われたので、平衡度が 1 つ増え 2 になり、修正が必要になります。この場合、平衡度が狂った節Ａと、その左側の節Ｂを、順序関係が崩れないように交換します。これを「ＬＬ１重回転」といいます。修正後は次のようになります。平衡度ＢＡ：0 ／＼ＤＡＢ：0 ／／＼ＦＥＣＤ：1 Ｆ < Ｄ < Ｂ < Ｅ < Ａ < Ｃ図 2 : ＬＬ１重回転（修正後）次も、左部分木が高くなる場合です。平衡度平衡度ＡＡ：1 ＡＡ：2 ／＼／＼ＢＣＢ：0 ＢＣＢ：-1 ／＼／＼ＤＥＤ：0 ＤＥＥ：1 ／ＦＦ：0 図 3 : ＬＲ２重回転（修正前）今度は、節Ｅの左側に節Ｆを追加します。Ｅの平衡度は 1 になりますが、Ｂから見ると右側の部分木に追加されていますので、平衡度を 1 つ減らして -1 となります。その親のＡは、左側の部分木に追加されていますので、平衡度を 1 増やし 2 になります。ＬＬ１重回転と同じく、節Ａの平衡度が 2 になりますが、節Ｂの平衡度が -1 になるので、区別することができます。この場合はＢとＥを交換してから、さらにＥとＡを交換します。これを「ＬＲ２重回転」といいます。修正後は次のようになります。平衡度ＥＡ：-1 ／＼ＢＡＢ：0 ／＼＼ＤＦＣＥ：0 Ｄ < Ｂ < Ｆ < Ｅ < Ａ < Ｃ図 4 : ＬＲ２重回転（修正後）節Ｆを節Ｅの右側に追加しても、ＬＲ２重回転となります。ただし、修正後の平衡度が異なります。平衡度平衡度ＡＡ：2 ＥＡ：0 ／＼／＼ＢＣＢ：-1 ＢＡＢ：1 ／＼／／＼ＤＥＥ：-1 ＤＦＣＥ：0 ＼ＦＦ：0 (1) 修正前 (2) 修正後Ｄ < Ｂ < Ｅ < Ｆ < Ａ < Ｃ図 5 : ＬＲ２重回転（その２）右の部分木が高くなる場合を考えましょう。平衡度平衡度ＡＡ：-1 ＡＡ：-2 ／＼／＼ＢＣＣ：0 ＢＣＣ：-1 ／＼／＼ＤＥＥ：0 ＤＥＥ：-1 ＼ＦＦ：0 図 6 : ＲＲ１重回転（修正前）最初の状態は、節Ａからみて右部分木が高いので、平衡度は -1 になっています。その他の節の平衡度は 0 です。この状態から節Ｅの右側に節Ｆを追加することを考えます。節Ｅの平衡度は -1 になります。節Ｃの平衡度は、右側の部分木に追加されたので、1 つ減らして -1 になります。その親のＡは、これも右部分木に追加されているので、平衡度を 1 つ減らして -2 になり、修正が必要になります。この場合、二分探索木の条件を崩さないように、節Ａと節Ｃを交換します。これを「ＲＲ１重回転」といいます。修正後は次のようになります。平衡度ＣＡ：0 ／＼ＡＥＣ：0 ／＼＼ＢＤＦＥ：-1 Ｂ < Ａ < Ｄ < Ｃ < Ｅ < Ｆ図 7 : ＲＲ１重回転（修正後）１重回転の次は、２重回転です。平衡度平衡度ＡＡ：-1 ＡＡ：-2 ／＼／＼ＢＣＣ：0 ＢＣＣ：1 ／＼／＼ＤＥＤ：0 ＤＥＤ：1 ／ＦＦ：0 図 8 : ＲＬ２重回転（修正前）節Ｄの左側に節Ｆを追加します。Ｄの平衡度は 1 になります。節Ｃは、左部分木に追加されたので、平衡度を１つ増やして 1 になります。その親のＡは、右部分木に追加されたので、平衡度を１つ減らして -2 となります。ＲＲ１重回転と同様に、節Ａの平衡度は -2 ですが、節Ｃの平衡度が 1 なので区別することができます。この場合、二分探索木の構成を崩さないように、節Ｄと節Ｃを交換して、さらに節Ｄと節Ａを交換します。これを「ＲＬ２重回転」といいます。修正後は次のようになります。平衡度ＤＡ：0 ／＼ＡＣＣ：-1 ／＼＼ＢＦＥＤ：0 Ｂ < Ａ < Ｆ < Ｄ < Ｃ < Ｅ図 9 : ＲＬ２重回転（修正後）節Ｄの右側に節Ｆを追加してもＲＬ２重回転となりますが、修正後の平衡度が異なります。平衡度平衡度ＡＡ：-2 ＤＡ：1 ／＼／＼ＢＣＣ：1 ＡＣＣ：0 ／＼／／＼ＤＥＤ：-1 ＢＦＥＤ：0 ＼ＦＦ：0 (1) 修正前 (2) 修正後Ｂ < Ａ < Ｄ < Ｆ < Ｃ < Ｅ図 10 : ＲＬ２重回転（その２）修正が必要なのは、以上６通りのパターンです。 ━━ ここまで ━━ AVL 木は二分探索木の一種ですから、二分探索木を継承することでデータの探索と表示を行うメソッドをそのまま再利用することができます。データを挿入する場合、平衡度を修正する処理が必要になるので、データ挿入のメソッドはオーバーライドしなければいけません。それでは具体的にプログラムします。最初にクラスと継承を設定します。 List 1 : クラスの設定 1 use Bintree; 2 3 package Avltree; 4 @ISA = (Bintree); 5 6 # 終端を表す nil を再ブレスする 7 sub make_tree { 8 $nil = Bintree->make_tree(); 9 bless $nil, 'Avltree'; 10 $nil; 11 } 終端を表す $nil は、クラス Bintree で定義されたオブジェクトを使わないと、データの探索や表示を行うメソッドは動作しません。そこで、AVL 木を初期化するメソッド make_tree で、Bintree->make_tree() を呼び出して終端を表すオブジェクトを取得し、大域変数 $nil にセットしておきます。また、このオブジェクトは Bintree にブレスされているので、オーバーライドしたメソッドを動作させるために、Avltree に再ブレスしておきます。次は節を生成するメソッドを作ります。 List 2 : 節を作る 1 sub new { 2 my ($type, $item) = @_; 3 my $obj = { 4 'item' => $item, 5 'left' => $nil, 6 'right' => $nil, 7 'balance' => 0 8 }; 9 bless $obj, $type; 10 $obj; 11 } 平衡度を表すため、節に新しい変数 balance を追加します。新しい節なので、平衡度は 0 に初期化します。 ○データの挿入次は、データの挿入を作成します。新しい節を挿入した場合、根の方に向かって平衡度をチェックしていく処理が必要になります。二分探索木では、データの挿入を再帰呼び出しでプログラムしましたが、平衡度のチェックを組み込むには少々面倒なので、ループに展開することにします。単純なループでは、たどってきた道筋がわからなくなるので、自前のスタックを用意して通過した節を記憶します。プログラムは次のようになります。 List 3 : AVL 木へデータを挿入 1 sub insert_tree { 2 my ($root, $item) = @_; 3 my @stack = (); 4 my $place = \$root; 5 while( $$place != $nil ){ 6 my $node = $$place; 7 my $result = $item->compare( $node->{'item'} ); 8 push( @stack, $node ); 9 if( $result == 0 ){ 10 return $root; # 同じデータ有り 11 } elsif( $result < 0 ){ 12 $place = \$node->{'left'}; 13 } else { 14 $place = \$node->{'right'}; 15 } 16 } 17 my $obj = Avltree->new($item); 18 return $obj if $root == $nil; # ルートに挿入 19 $$place = $obj; 20 &check_balance( $root, $obj, \@stack ); 21 } メソッド insert_tree は AVL 木のルートと挿入するデータを受け取り、挿入した後の木を返します。これは二分探索木の場合と同じです。道筋を記憶するために配列 @stack を用意します。変数 $place は、節を格納する変数を指し示すリファレンスを格納します。$place の使い方が、このプログラムのポイントです。リファレンスを使うことで、そこに格納されている節を取り出したり、そこへ新しい節をセットすることができます。最初は $root へのリファレンスで初期化します。 5 - 16 行目の while ループで、データを挿入する場所を求めるために木をたどります。7 行目で、$place が指し示す変数から節を取り出し $node にセットします。8 行目でデータを比較し、9 行目で節 $node を @stack に格納します。 $result が 0 より小さい場合は $place に $node->{'left'} へのリファレンスを、大きい場合は $node->{'right'} へのリファレンスをセットします。これで $$place とすれば、次の節にアクセスすることができます。ループを抜けたら、新しい節を作成して木に挿入します。$root が $nil であれば空の木なので、新しい節 $obj を返します。そうでなければ、木に新しい節 $obj を挿入します。$place は $node->{'left'} か $node->{'right'} へのリファレンスなので、$$place に $obj を代入するだけで、正しい位置に節が挿入されます。最後に、関数 check_balance を呼び出して、木の平衡度をチェックします。この時、ルートを書き換える場合があるので、check_balance でルートを返すようにします。 ○平衡度のチェック次は check_balance を作ります。 List 4 : バランスのチェック 1 sub check_balance { 2 my ($root, $node, $stack) = @_; 3 my $cnode = $nil; 4 my ($b, $pnode); 5 for( ; @$stack > 0; $node = $pnode ){ 6 $pnode = pop( @$stack ); 7 if( $pnode->{'left'} == $node ){ 8 $b = ++$pnode->{'balance'}; 9 } else { 10 $b = --$pnode->{'balance'}; 11 } 12 return $root if $b == 0; # 書き換え必要無し 13 if( $b > 1 ){ 14 $cnode = &LR_rotate( $node, $pnode ); 15 last; 16 } elsif( $b < -1 ) { 17 $cnode = &RL_rotate( $node, $pnode ); 18 last; 19 } 20 } 21 # 子の付け替え処理(List 5) 22 } スタックに積まれた節を取りだして、平衡度をチェックしていきます。$node は、新しい節が追加された部分木を表します。この関数が呼び出された時は、新しく追加された節が渡されます。$node の親を $pnode とします。5 行目の for ループで、スタックにデータがある間、平衡度をチェックします。6 行目で、スタックから $node の親を取り出して $pnode にセットします。7 行目で、$node が $pnode の left か right のどちらに挿入されているか調べます。left ならば平衡度を +1 し、right ならば -1 します。 12 行目で、平衡度 $b が 0 ならば木のバランスは保たれているので、それ以上チェックする必要はありません。ルートは変更する必要がないので、$root をそのまま返します。 13 行目で、$b が 1 より大きくなったのであれば、木を修正する必要があります。この場合は、左部分木が大きいのでＬＬ１重回転かＬＲ２重回転の処理が必要です。この処理は LR_rotate で行います。この関数は修正後の部分木を返すので、それを $cnode に格納してループを抜けます。 16 行目で、$b が -1 より小さいのであれば、右部分木が大きくなったので、ＲＲ１重回転かＲＬ２重回転の処理が必要になります。この処理は RL_rotateで行います。これ以外は、修正が必要なほど平衡度が崩れていない場合です。$node を $pnode に更新して、次の親をチェックします。ループを抜けた後、平衡度が崩れた部分木は修正されていますが、その部分木を持つ節の書き換えが済んでいません。次の図を見てください。Ｐ平衡度Ｐ平衡度＼＼ＡＡ：-2 ＤＡ：1 ／＼／＼ＢＣＣ：1 ＡＣＣ：0 ／＼／／＼ＤＥＤ：-1 ＢＦＥＤ：0 ＼ＦＦ：0 (1) 修正前 (2) 修正後図 11 : 子の付け替えが必要（例：ＲＬ２重回転）図 11 において、節Ａで木の修正が行われた場合、節Ｐの右側の子をＡからＤに付け替えなければいけません。回転処理を行う関数は、節Ｄを返しますので、子の付け替え処理を行います。 List 5 : 子の付け替え処理 1 if( @$stack > 0 ){ 2 my $ppnode = pop( @$stack ); 3 if( $ppnode->{'left'} == $pnode ){ 4 $ppnode->{'left'} = $cnode; 5 } else { 6 $ppnode->{'right'} = $cnode; 7 } 8 } elsif( $cnode != $nil ){ 9 return $cnode; 10 } 11 $root; もしスタックにデータがあれば、そこから節を取り出して $ppnode にセットします。この節は $pnode の親なので、$pnode が格納されている変数に $cnode をセットします。スタックにデータがない場合は、ルートを書き換えるため $cnode を返します。ただし、$cnode が NULL の場合は、部分木の修正が行われていないので $root をそのまま返します。 ○バランスの修正後は、部分木を修正する回転処理です。これは、図を見ながらコーディングするだけです。この処理を行う関数には、平衡度の崩れた節を $pnode とし、その子を $node として渡します。まずＬＲ回転処理からです。$node の平衡度が -1 の場合はＬＲ２重回転です。Ａ：$pnode, Ｂ：$node, Ｅ：$cnode にあたる平衡度平衡度ＡＡ：2 ＥＡ：0 ／＼／＼ＢＣＢ：-1 ＢＡＢ：1 ／＼／／＼ＤＥＥ：-1 ＤＦＣＥ：0 ＼ＦＦ：0 (1) 修正前 (2) 修正後Ａ->{'left'} = Ｅ->{'right'}; Ｂ->{'right'} = Ｅ->{'left'}; Ｅ->{'right'} = Ａ; Ｅ->{'left'} = Ｂ; 図 12 : ＬＲ２重回転のポインタの付け替え図の例では、Ｅ->{'left'} は $nil ですので、Ｂ->{'right'} に直接 $nil をセットしたくなりますが、ＬＲ２重回転の場合は、Ｅ->{'right'} が $nil でＥ->{'left'} に節がある、という別パターンがありますので、直接 $nil をセットしてはいけません。ポインタを付け替えたら平衡度を書き換えます。$cnode の平衡度によって $pnode と $node の平衡度が違いますので、注意してください。 $node の平衡度が -1 以外であればＬＬ１重回転です。これも図を見たほうがわかりやすいでしょう。Ａ：$pnode, Ｂ：$node にあたる平衡度平衡度ＡＡ：2 ＢＡ：0 ／＼／＼ＢＣＢ：1 ＤＡＢ：0 ／＼／／＼ＤＥＤ：1 ＦＥＣＤ：1 ／ＦＦ：0 (1) 修正前 (2) 修正後Ａ->{'left'} = Ｂ->{'right'}; Ｂ->{'right'} = Ａ; 図 13 : ＬＬ１重回転のポインタの付け替え後は $pnode と $node の平衡度を 0 にすれば修正完了です。ＬＬ１重回転の場合、Ｂが関数の返り値になります。これをプログラムすると、次のようになります。 List 6 : LR 回転 1 sub LR_rotate { 2 my ($node, $pnode) = @_; 3 my $cnode, $b; 4 if( $node->{'balance'} < 0 ){ 5 $cnode = $node->{'right'}; 6 $pnode->{'left'} = $cnode->{'right'}; 7 $node->{'right'} = $cnode->{'left'}; 8 $cnode->{'right'} = $pnode; 9 $cnode->{'left'} = $node; 10 if( $cnode->{'balance'} > 0 ){ 11 $pnode->{'balance'} = -1; 12 $node->{'balance'} = 0; 13 } elsif( $cnode->{'balance'} < 0 ){ 14 $pnode->{'balance'} = 0; 15 $node->{'balance'} = 1; 16 } else { 17 $pnode->{'balance'} = 0; 18 $node->{'balance'} = 0; 19 } 20 $cnode->{'balance'} = 0; 21 } else { 22 $pnode->{'left'} = $node->{'right'}; 23 $node->{'right'} = $pnode; 24 $pnode->{'balance'} = 0; 25 $node->{'balance'} = 0; 26 $cnode = $node; 27 } 28 $cnode; 29 } プログラムは少々長いですが、図と同じように節を付け替えているだけです。ＬＲ２重回転の場合、$node と $pnode の平衡度は $cnode の平衡度により異なり、次の３通りの場合があります。Ａ：$pnode, Ｂ：$node, Ｅ：$cnode にあたる平衡度平衡度ＡＡ：2 ＥＡ：0 ／＼／＼ＢＣＢ：-1 ＢＡＢ：1 ／＼／／＼ＤＥＥ：-1 ＤＦＣＥ：0 ＼ＦＦ：0 修正前修正後 (1) $cnode の平衡度が -1 の場合平衡度平衡度ＡＡ：2 ＥＡ：-1 ／＼／＼ＢＣＢ：-1 ＢＡＢ：0 ／＼／＼＼ＤＥＥ：1 ＤＦＣＥ：0 ／ＦＦ：0 修正前修正後 (2) $cnode の平衡度が 1 の場合平衡度平衡度ＡＡ：2 ＥＡ：0 ／／＼ＢＢ：-1 ＢＡＢ：0 ＼ＥＥ：0 Ｅ：0 修正前修正後 (3) $cnode の平衡度が 0 の場合図 14 : 平衡度の書き換え「Ｚしーモンキーほしゅうの時間その１０(月刊・電脳倶楽部 Vol.95 ZFIX10.DOC)」で作成したプログラムは、図 14 (3) のチェックが抜けていたため、平衡度の値がおかしくなる不具合が発生します。なんとまあ、４年前に作ったプログラムのバグを見つけることになるとは思ってもいませんでした。開き直って、AVL 木を取り上げて良かったということでしょうか（笑）。まあ、木のバランスは少々おかしくなりますが、二分探索木としての機能は正常に動作します。どの程度の影響があるのか、実際にプログラムを修正して試してみました。すると、データの比較回数は 1 - 2 % 減少しますが、実行速度はわずかながら遅くなってしまいました。つまり、AVL 木ではバランスの修正に時間がかかるのです。AVL 木には実用的な価値があまりないと評価されるのも、これが原因なのです。ＲＲ１重回転とＲＬ２重回転の処理は、RL_rotate で行います。処理内容は LR_rotate と同じなので、図のみ示すことにします。Ａ：$pnode, Ｃ：$node にあたる平衡度平衡度ＡＡ：-2 ＣＡ：0 ／＼／＼ＢＣＣ：-1 ＡＥＣ：0 ／＼／＼＼ＤＥＥ：-1 ＢＤＦＥ：-1 ＼ＦＦ：0 (1) 修正前 (2) 修正後Ａ->{'right'} = Ｃ->{'left'}; Ｃ->{'left'} = Ａ; 図 15 : ＲＲ１重回転のポインタの付け替えＡ：$pnode, Ｃ：$node, Ｄ：$cnode にあたる平衡度平衡度ＡＡ：-2 ＤＡ：1 ／＼／＼ＢＣＣ：1 ＡＣＣ：0 ／＼／／＼ＤＥＤ：-1 ＢＦＥＤ：0 ＼ＦＦ：0 (1) 修正前 (2) 修正後Ａ->{'right'} = Ｄ->{'left'}; Ｃ->{'left'} = Ｄ->{'right'}; Ｄ->{'left'} = Ａ; Ｄ->{'right'} = Ｃ; 図 16 : ＲＬ２重回転のポインタの付け替えプログラムの詳細はソースファイル avltree.pm を読んでください。 ○実行結果それでは、実際に実行してみましょう。木の形を表示するために、データを表示する関数 print_tree_test を Bintree に追加します。 List 7 : 木の形を表示 1 sub print_tree_test { 2 my ($node, $level) = @_; 3 my $i; 4 if( $node != $nil ){ 5 &print_tree_test( $node->{'left'}, $level + 1 ); 6 for( $i = 0; $i < $level; $i++ ){ 7 print " "; 8 } 9 $node->{'item'}->print_object(); 10 &print_tree_test( $node->{'right'}, $level + 1 ); 11 } 12 } データを出力する前に、レベル * 2 個の空白を出力します。これで木の形を表すことができます。テストデータは第１６回と同様に数値とします。最初に二分探索木へ 1 から 7 までのデータを順番に挿入します。 # テストプログラム $root = Bintree->make_tree(); for( $i = 1; $i <= 7; $i++ ){ my $obj = Number->new( $i ); $root = $root->insert_tree( $obj ); } $root->print_tree_test( 0 ); 実行結果 1 2 3 4 5 6 7 実行結果を見ればおわかりのように、右側の木にしかデータが挿入されません。これが二分探索木での最悪の状態です。では、AVL 木を使ってみましょう。 # テストプログラム $root = Avltree->make_tree(); for( $i = 1; $i <= 7; $i++ ){ my $obj = Number->new( $i ); $root = $root->insert_tree( $obj ); } $root->print_tree_test( 0 ); 実行結果 1 2 3 4 5 6 7 このように、木のバランスは完全に保たれています。プログラムは正常に動作していますね。 ○次回は？電脳倶楽部が Vol.147 で休刊になるのはとても残念です。残り２回しかありませんが、最後まで続けるのでよろしくお付き合いくださいませ。次回は Perl のオブジェクト指向と密接に関連しているパッケージ機能について、最終回は変数とクラスを結び付ける働きをするタイについて説明する予定です。お楽しみに。 ―参考文献― [1] 村田敏幸「X68000マシン語プログラミング木探索」 Oh!X 1993 年 7 月号ソフトバンク [2] 近藤嘉雪「定本Ｃプログラマのためのアルゴリズムとデータ構造」ソフトバンク 1998 [3] Larry Wall, Tom Christiansen, Randal L. Schwartz 共著「プログラミングＰｅｒｌ」改訂版オライリー・ジャパン 1997 [4] Sriram Srinivasan 著「実用Ｐｅｒｌプログラミング」オライリー・ジャパン 1998 （ＥＯＦ）